package com.leetcode.No0472;

import org.junit.Test;

import java.util.*;

/**
 * @program: Solution
 * @description: 连接词
 *      超时了。。。
 * @author: Wang Zhihua
 * @date: 2021-12-28
 */
public class Solution {

    @Test
    public void test01() {
        String[] words = new String[]{"cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"};
        System.out.println(findAllConcatenatedWordsInADict(words));

        words = new String[]{"cat","dog","catdog"};
        System.out.println(findAllConcatenatedWordsInADict(words));
    }

    private Node head = new Node();
    private boolean isConjunction = false;

    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        ArrayList<String> result = new ArrayList<>();

        TreeSet<Integer> lenSet = new TreeSet<>();
        for (String word : words) {
            lenSet.add(word.length());
        }

        if (lenSet.size() <= 1) {
            return result;
        }

        Arrays.sort(words, Comparator.comparingInt(String::length));

        int len = words.length;
        int currInd = 0;
        Integer currLen = lenSet.pollFirst();
        Integer nextLen = lenSet.first();
        String currStr;
        while (currLen != null && nextLen != null) {
            while (currInd < len && (currStr = words[currInd]).length() == currLen) {
                putStr2Tree(currStr);
                ++currInd;
            }
            for (int i = currInd; i < len && words[i].length() == nextLen; ++i) {
                if (checkConjunction(words[i])) {
                    result.add(words[i]);
                }
            }
            currLen = lenSet.pollFirst();
            nextLen = lenSet.isEmpty() ? null : lenSet.first();
        }

        return result;
    }

    private boolean checkConjunction(String str) {
        char[] chars = str.toCharArray();
        if (head.sonMap.get(chars[0]) == null) {
            return false;
        }
        isConjunction = false;
        checkFunc(chars, head, 0);
        return isConjunction;
    }

    private void checkFunc(char[] chars, Node fatherNode, int index) {
        if (isConjunction || index >= chars.length) {
            return;
        }
        Node currNode = fatherNode.sonMap.get(chars[index]);
        if (currNode == null) {
            return;
        }
        if (index == chars.length - 1) {
            isConjunction = currNode.isEnd;
            return;
        }
        if (currNode.isEnd) {
            checkFunc(chars, head, index + 1);
        }
        checkFunc(chars, currNode, index + 1);
    }

    private void putStr2Tree(String str) {
        Node currNode = head;
        char[] chars = str.toCharArray();
        for (char ch : chars) {
            Node sonNode = currNode.sonMap.get(ch);
            if (sonNode == null) {
                currNode.sonMap.put(ch, sonNode = new Node());
            }
            currNode = sonNode;
        }
        currNode.isEnd = true;
    }

    private class Node {
        Map<Character, Node> sonMap = new HashMap<>(); // 子节点
        boolean isEnd = false;
    }

}
